Bagaimana kita secara matematis menggambarkan benang-benang tak terlihat yang menghubungkan masyarakat? Baik itu Angka Bacon yang menghubungkan Bela Lugosi dengan tokoh-tokoh ikonik Hollywood atau Graf Kekeliruan pengelompokan titik-titik data berdasarkan jarak dekat, Teori Graf memberikan bahasa formal $G = (V, E)$ untuk memodelkan alam semesta diskret ini.
1. Anatomi Graf
Pada dasarnya, sebuah graf terdiri dari himpunan simpul ($V$) dan himpunan sisi ($E$). Namun, aturan-aturan yang diterapkan bervariasi tergantung pada struktur:
- Graf Sederhana: Bentuk yang paling elegan; melarang loop (sisi yang menghubungkan simpul ke dirinya sendiri) dan sisi paralel (sisi ganda antara dua titik yang sama).
- Multigraf: Mengizinkan loop dan sisi paralel, sering digunakan untuk memodelkan berbagai jenis interaksi (misalnya teks vs panggilan) antara dua simpul yang sama.
- Simpul Terasing: Sebuah simpul $v$ dikatakan terasing jika tidak ada sisi yang bersinggungan dengannya, merepresentasikan objek tanpa hubungan dalam himpunan saat ini.
Dalam ilmu data, kita sering menggunakan fungsi Fungsi Ketidaksamaan untuk membuat graf:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
Kita menggambar sisi antara $v$ dan $w$ hanya jika $s(v, w)$ berada di bawah ambang tertentu, secara efektif membangun jaringan "tetangga".
2. Jalur, Konektivitas, dan Komponen
Sebuah jalur adalah urutan simpul dan sisi. Jika suatu jalur tidak mengunjungi simpul lebih dari sekali, maka disebut jalur sederhana. Konektivitas adalah denyut nadi graf:
- Graf Terhubung: Terdapat jalur antara setiap pasangan simpul dalam graf.
- Komponen: Jika graf tidak terhubung, maka akan terpecah menjadi bagian-bagian yang saling terpisah yang disebut komponen. Setiap komponen merupakan subgraf terhubung maksimal.
3. Subgraf: Arsitektur Himpunan Bagian
Subgraf $G' = (V', E')$ adalah himpunan bagian dari graf $G$ sedemikian sehingga setiap simpul di $V'$ ada di $V$, dan setiap sisi di $E'$ menghubungkan simpul-simpul yang ditemukan di $V'$. Mengidentifikasi subgraf sangat penting untuk mendeteksi pola lokal dalam jaringan global.